
109
In practice, the running time of all the balanced tree
schemes is worse (by a constant factor) than the simple binary
search tree, but this is generally acceptable in view of the
protection being given against easily obtained worst-case input.
A final note: By inserting elements into a search tree and
then performing an inorder traversal, we obtain the elements in
sorted order. This gives an O(n log n) algorithm to sort, which is a
worst-case bound if any sophisticated search tree is used.
References:
1. G. M. Adelson-Velskii and E. M. Landis, "An Algorithm for the
Organization of Information," Soviet Math. Doklady 3.
2. A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and
Analysis of Computer Algorithms, Addison-Wesley, Reading,
MA, 1974.
3. B. Allen and J. I. Munro, "Self Organizing Search Trees,"
Journal of the ACM, 25 (1978).
4. R. A. Baeza-Yates, "Expected Behaviour of B
+
- trees under
Random Insertions," Acta Informatica 26 (1989).
5. R. A. Baeza-Yates, "A Trivial Algorithm Whose Analysis Isn't: A
Continuation," BIT 29 (1989).
6. R. Bayer and E. M. McGreight, "Organization and Maintenance
of Large Ordered Indices," Acta Informatica 1 (1972).
7. J. L. Bentley, "Multidimensional Binary Search Trees Used for
Associative Searching," Communications of the ACM 18 (1975).
8. Data structure – A Pseudocode Approach with C – Richard F
Gilberg Behrouz A. Forouzan, Thomson
9. Schaum’s Outlines Data structure Seymour Lipschutz Tata
McGraw Hill 2nd Edition
10.Data structures & Program Design in C Robert Kruse, C.
L.Tondo, Bruce Leung Pearson
11.“Data structure using C” AM Tanenbaum, Y Langsam & M J
Augustein, Prentice Hall India
Question Pattern
1. What are trees? Explain the different methods of tree traversals.
2. What are expression trees? Explain with examples.
3. Explain the AVL tree in detail.
4. What are splay trees? Explain in detail.
5. Explain the Binary search trees in detail.